#include<string>
#include<iostream>
#include<vector>
#include<stack>
using namespace std;

class Solution {
public:
    string removeDuplicates(string s) {
        string st;
        for (auto& ch : s) {
            if (!st.empty() && st.back() == ch) st.pop_back();
            else st += ch;
        }
        return st;
    }
};

class Solution {
public:
    bool backspaceCompare(string s, string t) {
        string st1;
        string st2;
        for (auto& ch : s) {
            if (!st1.empty() && ch == '#')
                st1.pop_back();
            else if (ch == '#');
            else st1 += ch;
        }
        for (auto& ch : t) {
            if (!st2.empty() && ch == '#')
                st2.pop_back();
            else if (ch == '#');
            else st2 += ch;
        }
        return st1 == st2;
    }
};


class Solution {
public:
    int calculate(string s) {
        char ch = '+';
        vector<int> st;
        int len = s.size();
        for (int i = 0; i < len; i++) {
            int tmp = 0;
            if (s[i] <= '9' && s[i] >= '0') {
                while (i < len && s[i] <= '9' && s[i] >= '0') {
                    tmp *= 10;
                    tmp += s[i] - '0';
                    i++;
                }
                if (ch == '+')
                    st.push_back(tmp);
                else if (ch == '-')
                    st.push_back(-1 * tmp);
                else if (ch == '*') {
                    st.back() *= tmp;
                }
                else if (ch == '/') {
                    st.back() /= tmp;
                }
            }
            if (s[i] == '+' || s[i] == '-' || s[i] == '*' || s[i] == '/') {
                ch = s[i];
            }
        }
        int ans = 0;
        for (auto& e : st) {
            ans += e;
        }
        return ans;
    }
};

class Solution {
public:
    string decodeString(string s) {
        vector<string> strs;
        strs.push_back("");
        stack<int> st;
        int len = s.size();
        for (int i = 0; i < len; i++) {
            if (s[i] >= '0' && s[i] <= '9') {
                int tmp = 0;
                while (i < len && s[i] >= '0' && s[i] <= '9') {
                    tmp *= 10;
                    tmp += s[i] - '0';
                    i++;
                }
                st.push(tmp);
            }
            if (s[i] == '[') {
                strs.push_back("");
                i++;
                while (i < len && s[i] >= 'a' && s[i] <= 'z') {
                    strs.back() += s[i];
                    i++;
                }
                if (s[i] >= '0' && s[i] <= '9') {
                    i--;
                    continue;
                }
            }
            if (s[i] == ']') {
                int digit = st.top();
                st.pop();
                string tmps = strs.back();
                strs.pop_back();
                for (int j = 0; j < digit; j++) {
                    strs.back() += tmps;
                }
            }
            if (s[i] >= 'a' && s[i] <= 'z') {
                while (i < len && s[i] >= 'a' && s[i] <= 'z') {
                    strs.back() += s[i];
                    i++;
                }
                i--;
            }
        }
        for (auto& e : strs) {
            cout << e << endl;
        }
        return strs.back();
    }
};
int main()
{
    string s("3[a2[c]]");
    Solution().decodeString(s);
    return 0;
}

class Solution {
public:
    bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
        stack<int> st;
        int i = 0;
        for (auto& e : pushed) {
            st.push(e);
            while (!st.empty() && st.top() == popped[i]) {
                st.pop();
                i++;
            }
        }
        return st.empty();
    }
};